The present invention generally relates to cryptosystems, and more particularly relates to private-key stream cipher cryptosystems which combine a keystream with plaintext to encrypt the plaintext into ciphertext and combine the ciphertext with a keystream to decipher the ciphertext into plaintext.
Cryptosystems perform cryptography to transform plaintext into ciphertext so that only an authorized receiver can transform the ciphertext back into the original plaintext. Encryption or enciphering is the process that transforms plaintext into ciphertext. Decryption or deciphering is the process that transforms ciphertext into plaintext.
A parameter called an encryption key is employed by a cryptosystem to prevent the plaintext from being easily revealed by an unauthorized person. A sender transforms a given plaintext into a large variety of possible ciphertext selected by the specific encryption key. A receiver of the ciphertext deciphers the ciphertext by employing a parameter referred to as a decryption key. In a public-key cryptosystem, the encryption key is made public while the decryption key is kept secret. Therefore, in public key cryptosystems, the decryption key must be computationally infeasible to deduce from the encryption key. In a private-key cryptosystem, the sender and the receiver typically share a common key that is used for both enciphering and deciphering. In such a private-key cryptosystem, the common key is alterable and must be kept secret.
Private-key cryptosystems are typically implemented as block cipher cryptosystems or stream cipher cryptosystems. Block cipher cryptosystems divide the plaintext into blocks and encipher each block independently using a stateless transform. In block cipher cryptosystems if one fixed common private-key is employed to encipher different occurrences of a particular plaintext block, all of these occurrences are encrypted into identical corresponding ciphertext blocks. Therefore, the block size is preferably selected to be large enough to frustrate attacks from a cryptanalyst, which analyzes the occurrence frequencies of various patterns among the ciphertext blocks. Example block sizes are 64 bits and 128 bits.
In stream cipher cryptosystems, the plaintext is typically encrypted on a bit-by-bit or word-by-word basis using a stateful transform that evolves as the encryption progresses. In encrypting the plaintext binary data sequence for transmission as a ciphertext binary data sequence, the common private-key is a parameter which controls a pseudo-random number generator to create a long sequence of binary data referred to as a key stream. The stream cipher cryptosystem includes a cryptographic combiner which combines the keystream with the plaintext sequence. The cryptographic combiner is typically implemented with exclusive-or (XOR) bit-wise logic gates which perform bit-wise modulo-2 addition. The cryptographic combiner produces the ciphertext. At the receiver, the common private-key controls a receiver pseudo-random number generator to produce a decryption keystream. The decryption keystream is combined with a decryption combiner to decrypt the ciphertext to provide the plaintext to the receiver.
One problem with stream cipher cryptosystems is the difficulty of generating a long, statistically uniform, and unpredictable sequence of binary data in the keystream from a short and random key. Such sequences are desirable in the keystream in cryptography to make it impossible, given a reasonable segment of its data and sufficient computer resources, to find out more about the sequences.
There are four general requirements for cryptographically secure keystream pseudo-random number generators. First, the period of a keystream must be large enough to accommodate the length of the transmitted message. Second, the keystream output bits must have good statistical properties (e.g. values are uniformally distributed). Third, the keystream output bits must be easy to generate. Fourth, the keystream output bits must be hard to predict. For example, given the pseudo-random number generator and the first N output bits, a(0), a(1), . . . , a(Nxe2x88x921), it should be computationally infeasible to predict the (N+1)th bit a(N) in a sequence with better than a 50xe2x80x9450 chance. In otherwords, a cryptanalyst should not be able to generate other forward bits or backward bits if presented with a given portion of the keystream output sequence.
The receiver decryption combiner operation must be the inverse of the sender encryption combiner operation so that the same keystream can be used to encrypt the plaintext at the sender to form the ciphertext and decrypt the ciphertext at the receiver to form the plaintext. The most common combiner operation is bit-wise XOR. One problem with the XOR combiner operation is that an accidental double encryption causes all of the plaintext to become visible. Another problem with the XOR combiner operation is that two ciphertext using the same key can be XORed together by a cryptanalyst to eliminate the keystream and leave the XOR of two plaintext. The low entropy of languages, such as the English language, allows for the XOR of two plaintexts to be resolved into its two original plaintext messages. Furthermore, if the keystream period is smaller than a message, this type of cryptanalysis also can be performed by dividing a ciphertext message into portions the size of the keystream and XORing the portions together to eliminate the keystream and leave the XOR of the plaintext portions.
A cryptographic combiner using a two""s compliment addition combiner operation has problems similar the XOR combiner operation. Accidental double encryption causes the least significant bit of each plaintext unit to become visible. In many cases, cryptanalysis can be performed to break the cipher with just the least significant bit of the plaintext being visible. Moreover, adding together 2N ciphertexts encrypted in the same keystream eliminates the key from the bottom N bits of each text unit and leaves the sum of 2N plaintexts for these bits. The low entropy of languages, such as the English language, often allow these N bits to be resolved into the N original plaintext messages, which in many cases can be used by a cryptanalyst to break a cipher. For example, cryptanalysis can be performed by dividing a ciphertext message into N pieces and adding the N pieces together.
Another problem with the XOR combiner operation is that it allows an adversary to manipulate the contents of the message with only trivial information about its structure. If an adversary wants to change some bit(s) in the received plaintext, all that need be done is to intercept the ciphertext message, invert the ciphertext bit(s) corresponding to the plaintext bit(s) the adversay wants to change, and then send the message on to the receiver. The only knowledge that an adversary needs is the location within the message of the bit(s) to be changed. A two""s complement combiner makes the manipulation a little more difficult in that the adversary will need to know the plaintext of all bits above (more significant than) the bit(s) to be changed. This knowledge is needed so the adversary can make the desired changes without carry or borrow changing other bits of the message that the adversary doesn""t want changed.
Some very complex cryptographic combiners solve some of the above-problems with the XOR combiner operation. These very complex cryptographic combiners are, however, quite expensive in terms of time and/or hardware resources. One example cryptographic combiner in this very complex category is a permutation table combiner. The permutation table is required to have a table the size of the plaintext alphabet. For example, if the plaintext unit size is 32 bits, the permutation table needs to be 16 gigabytes. On the other hand, if the plaintext unit size is 8 bits, the permutation table size is only required to be 256 bytes, but encrypting 8 bit plaintext units is typically 4 times slower than using 32 bit plaintext units. In addition, the smaller plaintext unit size limits the amount of plaintext diffusion. Plaintext diffusion means that plaintext bits can effect the encryption of other plaintext bits. For example, the XOR combiner operation has no plaintext diffusion.
Often, the ciphertext produced by encryption must not contain a value that is reserved to mean end-of-string, end-of-message, or end-of-file. For example, a text string in the C programming language cannot contain a zero byte because that value is reserved to mean end-of-string. The simple XOR and two""s complement combiners can produce any ciphertext value. This means that extra effort must be applied to prevent the reserved values from appearing within the ciphertext.
For reasons stated above and for other reasons presented in greater detail in the Description of the Preferred Embodiments section of the present specification, a cryptographic combiner is desired for stream cipher cryptosystems wherein accidental double encryption does not remove the keystream from the combined output bits. In addition, there is a need for a cryptographic combiner where the same keystream cannot be used to combine two ciphertext to eliminate the keystream and leave the combiner operation of the two original plaintext messages. In addition, there is a need for a cryptographic combiner that produces ciphertext which is known not to contain some reserved value. Such a desired cryptographic combiner should be relatively inexpensive in time and hardware resources.
The present invention provides a stream cipher cryptosystem including a pseudo-random number generator receiving a key and providing a keystream. The stream cipher cryptosystem also includes a cryptographic combiner receiving a first binary data sequence and the keystream. The cryptographic combiner performs a one""s complement operation on the first binary data sequence and the keystream to provide a second binary data sequence.
In encryption operations, the cryptographic combiner is an encryption combiner and the first binary data sequence is a plaintext binary data sequence and the second binary data sequence is a ciphertext binary data sequence. In decryption operations, the cryptographic combiner is a decryption combiner and the first binary data sequence is a ciphertext binary data sequence and the second binary data sequence is a plaintext binary data sequence.
In one embodiment, the one""s complement operation is a one""s complement addition operation. In another embodiment, the one""s complement operation is a one""s complement subtraction operation. In one embodiment, the stream cipher cryptosystem includes a controller for controlling the cryptographic combiner to select the one""s complement operation from an addition operation and a subtraction operation. In one embodiment, the controller controls the cryptographic combiner to pseudo-randomly select between the addition operation and the subtraction operation. In one embodiment, the controller controls the cryptographic combiner to select between the addition operation and the subtraction operation based on the amount of text currently processed.
In one embodiment, the cryptographic combiner is implemented in software and the one""s complement operation is an addition operation performed by a two""s complement addition. In this embodiment, a constant is added with an ADD WITH CARRY instruction to convert the two""s complement answer to a one""s complement answer. In one embodiment, the constant used with an ADD WITH CARRY instruction is selected such that the ciphertext does not contain a reserved value. In another embodiment where the cryptographic combiner is implemented in software, the one""s complement operation is a subtraction operation performed by a two""s complement subtraction. In this embodiment, a constant is subtracted with a SUBTRACT WITH BORROW instruction to convert the two""s complement answer to a one""s complement answer. In one embodiment, the constant used with a SUBTRACT WITH BORROW instruction is selected such that the ciphertext does not contain a reserved value.
In one form of the present invention, a stream cipher cryptosystem includes an encryption pseudo-random number generator receiving a key and providing an encryption keystream. An encryption combiner receiving a first plaintext binary data sequence and the encryption keystream. The encryption combiner performs a first one""s complement operation on the first plaintext binary data sequence and the encryption keystream to provide a ciphertext binary data sequence. A decryption pseudo-random number generator receives the key and provides a decryption keystream. A decryption combiner receives the ciphertext binary data sequence and the decryption keystream. The decryption combiner performing a second one""s complement operation on the ciphertext binary data sequence and the decryption keystream to provide a second plaintext binary data sequence substantially similar to the first plaintext binary data sequence. In this form of the present invention, the second one""s complement operation is preferably the inverse of the first one""s complement operation.
The stream cipher cryptosystem according to the present invention includes one""s complement cryptographic combiner wherein accidental double encryption does not remove the keystream from the combined output bits. In the one""s complement cryptographic combiner operation according to the present invention, the same keystream cannot be used to combine two ciphertext to eliminate the keystream and leave the combiner operation of the two original plaintext messages. Nevertheless, the one""s complement cryptographic combiner operation according to the present invention requires a minimal increase of resources over a conventional XOR combiner operations.